import random
from copy import deepcopy

class Sudoku:
    def __init__(self, difficulty='medium'):
        self.size = 9
        self.box_size = 3
        self.difficulty = difficulty
        self.solution = None
        self.puzzle = None
        self.user_input = None
        self.__generate_full_grid()
        self.__generate_puzzle()

    def __generate_full_grid(self):
        """生成有效数独终盘"""
        def find_empty(board):
            for i in range(self.size):
                for j in range(self.size):
                    if board[i][j] == 0:
                        return (i, j)
            return None

        def is_valid(board, num, pos):
            row, col = pos
            # Check row
            if num in board[row]:
                return False
            # Check column
            if num in [board[i][col] for i in range(9)]:
                return False
            # Check box
            box_x = col // 3 * 3
            box_y = row // 3 * 3
            for i in range(box_y, box_y+3):
                for j in range(box_x, box_x+3):
                    if board[i][j] == num and (i,j) != pos:
                        return False
            return True

        def solve(board):
            empty = find_empty(board)
            if not empty:
                return True
            row, col = empty
            
            for num in random.sample(range(1,10), 9):
                if is_valid(board, num, (row, col)):
                    board[row][col] = num
                    if solve(board):
                        return True
                    board[row][col] = 0
            return False

        # 生成随机第一行
        board = [[0]*9 for _ in range(9)]
        board[0] = random.sample(range(1,10), 9)
        solve(board)
        self.solution = board

    def __generate_puzzle(self):
        """生成谜题"""
        puzzle = deepcopy(self.solution)
        holes = 81 - self._get_clues_count()
        positions = [(i,j) for i in range(9) for j in range(9)]

        for pos in random.sample(positions, k=81):
            if holes <= 0:
                break
            row, col = pos
            original = puzzle[row][col]
            puzzle[row][col] = 0

            if self.count_solutions(deepcopy(puzzle)) == 1:
                holes -= 1
            else:
                puzzle[row][col] = original

        self.puzzle = puzzle
        self.user_input = deepcopy(puzzle)

    def _get_clues_count(self):
        return {
            'debug': 75,
            'easy': 40,
            'medium': 35,
            'hard': 28
        }[self.difficulty]

    def count_solutions(self, grid):
        """计算解的个数"""
        def backtrack(pos=0):
            if pos == 81:
                nonlocal count
                count += 1
                return count > 1  # 发现第二个解时提前终止
            row, col = pos//9, pos%9
            
            if grid[row][col] != 0:
                return backtrack(pos+1)
            
            for num in random.sample(range(1,10),9):
                if self.is_valid(grid, num, (row,col)):
                    grid[row][col] = num
                    if backtrack(pos+1):
                        return True
                    grid[row][col] = 0
            return False

        count = 0
        backtrack()
        return count

    def is_valid(self, board, num, pos):
        """验证单个单元格"""
        row, col = pos
        # 检查行
        if num in board[row]:
            return False
        # 检查列
        if num in [board[i][col] for i in range(9)]:
            return False
        # 检查宫
        box_x = col//3 * 3
        box_y = row//3 * 3
        for i in range(box_y, box_y+3):
            for j in range(box_x, box_x+3):
                if board[i][j] == num and (i,j) != pos:
                    return False
        return True

    @property
    def remaining_empty(self):
        return sum(1 for row in self.user_input for cell in row if cell == 0)

    def validate(self):
        return all(self.user_input[i][j] == self.solution[i][j] 
                  for i in range(9) for j in range(9))

    def hint(self):
        empty = [(i,j) for i in range(9) for j in range(9) 
                if self.user_input[i][j] == 0]
        if not empty:
            return None
        row, col = random.choice(empty)
        return (row, col, self.solution[row][col])